KMP算法：求next数组，一听就会

KMP算法就是一种字符串匹配算法，简单说就是从一个长字符串中搜索一个短字符串（也叫模式串）。 这个算法我从大学上数据结构课第一次学到，到现在反反复复学过不下十次，每次都当时觉得懂了，可就是记不住，相信很多人也有同感。最记不住的地方就是next数组的求法。 今天我尝试着用尽量容易理解的方法去讲解这个问题，希望我自己和各位读者从此把这个算法牢牢记住。

前面的引子就不说了，KMP算法的关键在于next数组。next数组的作用是：匹配到某一位失败时，回退到next[i]这一位重新去匹配。

我这里自己定义一个名词“端长”，指的是字符串前缀和后缀相等的长度。比如字符串"ababa"的端长有3，1。因为前三位aba与后三位aba相等，长度为3，所以端长为3。第一位与最后一位也相同，所以1也是一个端长，但最大端长是3。 请记住这个“端长”的含义。我尝试过很多次去解释kmp算法的实现，发现这里必须有一个定义，才便于后面的描述和理解。

实际上，求next[i]的值就是求模式串第i个字符之前（不包括第i个）的子串的最大端长。 例如：模式串为ababacd，next[5]就是ababa这个字符串的最大端长，也就是3，所以next[5] = 3。

手动构造next数组的方法：前两位固定为-1和0，第三位，下标i=2，next[i] 的值为模式串p的前2位子串的最大端长，以此类推。对于手动构造，最大端长的值可以一眼看出来。

问题在于，对于一个字符串，最大端长的值用代码怎么求？暴力法当然可以，但太慢了，每一次都需要O(n)的时间复杂度，而我们现在需要求len(p)个字串的最大端长，这样的复杂度太高了。 关键点在这里：我们可以用递推的方法来求最大端长。求next数组的时候，我们是从0开始从前往后算的。对于next[i]的值，我们可以利用next[i-1]的值来计算。

要确定这样一个前提：如果一个字符串p的最大端长为k，那么这个字符串后面再加一位之后，最大端长最多只能是k+1，这是上限。而且要等于k+1还有个前提，就是加的这一个字符等于p[k]。 例如：字符串ababa的最大端长为3，如果在后面加一个b，ababab，则最大端长变为4，因为p[3]是b。

下面开始递推：假如next[i-1]的值为k，也就是模式串p的0到i-2位的最大端长为k，那么如果p[k] == p[i-1]，则可以得到结果：p的0到i-1为的最大端长为k+1，next[i] = k+1。

那如果p[k] != p[i-1]呢？可以继续寻找小一点的端长，这恰好是0到k-1字串的最大端长，把这个端长设为新的k，重复上面的步骤。

例如：如果要求ababaa的最大端长，先看去掉最后一位之后 ababa的最大端长是3，对应前缀是aba。但最后一位p[5]是a, 而p[3]是b，不相等。继续寻找ababa的下一个端长，其实也就是aba的最大端长1，正好p[1]是a，等于最后一位p[5]，所以ababaa的最大端长就是1。

这部分逻辑转化成Go语言代码就是这样：